package com.hqq.leetcode.tree;

import com.hqq.exercise.tree.TreeNode;
import com.hqq.exercise.tree.TreeNodeUtil;

import java.util.Stack;

/**
 * InvertTree 反转二叉树
 * Description:
 * Invert a binary tree.
 * <p>
 * Test Cases:
 * ----1         1
 * ---/ \       / \
 * --2   3  => 3   2
 * -----/       \
 * ----4         4
 * <p>
 * Created by heqianqian on 2017/9/13.
 */
public class InvertTree {

    public static void main(String[] args) {
        /*data preparation*/
        TreeNode root = new TreeNode(1);
        TreeNode rChild = new TreeNode(3);
        rChild.left = new TreeNode(4);
        root.left = new TreeNode(2);
        root.right = rChild;

        InvertTree it = new InvertTree();
        it.invertBinaryTree(root);
        TreeNodeUtil.levelTraversal(root);
    }

    /**
     * @param root: a TreeNode, the root of the binary tree
     */
    public void invertBinaryTree(TreeNode root) {
        // write your code here
        //invertRecursion(root);
        invertLoop(root);
    }

    /**
     * Implementation with recursion
     */
    private void invertRecursion(TreeNode root) {
        if (root == null) {
            return;
        }
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        if (root.left != null) {
            invertRecursion(root.left);
        }
        if (root.right != null) {
            invertRecursion(root.right);
        }
    }

    /**
     * Implementation with loop
     */
    private void invertLoop(TreeNode root) {
        if (root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.empty()) {
            TreeNode tmp = stack.pop();
            //交换左右子树
            TreeNode l = tmp.left;
            tmp.left = tmp.right;
            tmp.right = l;
            if (tmp.right != null) {
                stack.push(tmp.right);
            }
            if (tmp.left != null) {
                stack.push(tmp.left);
            }
        }
    }
}
